1364B - Most socially-distanced subsequence - CodeForces Solution

#include <bits/stdc++.h>
#include <time.h>
using namespace std;

#define vi vector<int>
#define f(i,a,b) for(int i=a;i<b;i++)
const int N= 1e5+5;
#define int long long
const int mod= 1e9+7;



signed main(){
ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
clock_t start=clock();
int tc=1;
cin>>tc;
 while(tc--){

   //logic:   for x,y,z. Chooose middle "y", iff diff(x,y)+diff(y,z)> diff(x,z)
    
   int n;cin>>n;
   vi arr(n),isPeak(n,0);
   f(i,0,n) cin>>arr[i];

   vector<int>ans;
   ans.push_back(arr[0]);// arr[0], always be the part
   ans.push_back(arr[1]);// need to check

   for(int i=2;i<n;i++){

    int size=ans.size();

    if(size<=1){
      ans.push_back(arr[i]);
      continue;
    }

    int x=ans[size-2],y=ans[size-1],z=arr[i];

    if(abs(x-y)+abs(y-z)<=abs(x-z))
      ans.pop_back();
    ans.push_back(z);  
   }

   cout<<ans.size()<<endl; 
   for(auto e:ans)
    cout<<e<<" ";

   cout<<endl; 
    

}
clock_t end=clock();
// double secs = double(end - start) / CLOCKS_PER_SEC;cerr << "\n\nTime elapsed : " << secs<<"s";
    return 0;
}